// https://leetcode-cn.com/problems/7WHec2/
#include <vector>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
		return split(head, nullptr);
    }

	ListNode * split(ListNode * head, ListNode * tail){
		if(head == nullptr){
			return head;
		}
		if(head->next == tail){
			head->next = nullptr; // 这里是必须的，防止最后两个元素的next是对方，导致无限循环
			return head;
		}
		ListNode * slow = head;
		ListNode * fast = head;
		while(fast != tail){
			slow = slow->next;
			fast = fast->next;
			if(fast != tail){
				fast = fast->next;
			}
		}
		ListNode * mid = slow;
		return sort(split(head, mid), split(mid, tail));
	}
	
	ListNode * sort(ListNode * head, ListNode * tail){
		ListNode * tmp = new ListNode;
		ListNode * tmpHead = tmp;
		while(head != nullptr && tail != nullptr){
			if(head->val < tail->val){
				tmp->next = head;
				head = head->next;
			}else{
				tmp->next = tail;
				tail = tail->next;
			}
			tmp = tmp->next;
		}
		if(head != nullptr){
			tmp->next = head;
		}else if(tail != nullptr){
			tmp->next = tail;
		}
		return tmpHead->next;
	}
	
	ListNode * init(vector<int> & elements){
		int len = elements.size();
		if(len == 0){
			return nullptr;
		}
		ListNode * head = new ListNode;
		head->val = elements[0];
		head->next = nullptr;
		ListNode * pos = head;
		for(int i = 1; i < len; i++){
			ListNode * tmp = new ListNode;
			tmp->val = elements[i];
			tmp->next = nullptr;
			pos->next = tmp;
			pos = pos->next;
		}
		return head;
	}
	
	void showListNode(ListNode * listNode){
		while(listNode){
			cout << listNode->val << " ";
			listNode = listNode->next;
		}
		cout << endl;
	}
};

int main(){
	vector<int> nums = {5, 1, 2, 3, 5, 4, 1};
	Solution so;
	ListNode * l = so.init(nums);
	so.showListNode(l);
	ListNode * head = so.sortList(l);
	so.showListNode(head);
	return 0;
}





ListNode* merge(ListNode* head1, ListNode* head2) {
	ListNode* dummyHead = new ListNode(0);
	ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
	while (temp1 != nullptr && temp2 != nullptr) {
		if (temp1->val <= temp2->val) {
			temp->next = temp1;
			temp1 = temp1->next;
		} else {
			temp->next = temp2;
			temp2 = temp2->next;
		}
		temp = temp->next;
	}
	if (temp1 != nullptr) {
		temp->next = temp1;
	} else if (temp2 != nullptr) {
		temp->next = temp2;
	}
	return dummyHead->next;
}






